package top.datacluster.basic.algorithm.leetcode.stack;

import java.util.Stack;

public class LeetCode844 {

    public boolean backspaceCompare(String S, String T) {
        Stack<Character> s = new Stack<>();
        for (int i = 0; i < S.length(); i++){
            if (S.charAt(i) == '#' && !s.isEmpty()){
                s.pop();
            }else{
                s.push(S.charAt(i));
            }
        }
        Stack<Character> t = new Stack<>();
        for (int i = 0; i < T.length(); i++){
            if (T.charAt(i) == '#' && !s.isEmpty()){
                t.pop();
            }else{
                t.push(S.charAt(i));
            }
        }
        if (s.size() != t.size()){
            return false;
        }
        while (!s.isEmpty() && !t.isEmpty()){
            if (s.pop() != t.pop()){
                return false;
            }
        }
        return true;
    }
}
